#include <stdio.h>
#include <stdlib.h>

typedef struct BSTreeNode {
	int value;
	struct BSTreeNode * left;
	struct BSTreeNode * right;
		
} BSTreeNode;


/**
 * ret val = 0 means neither n1 nor n2 is in the subtree rooted at root
 * ret val = 1 means that nodes n1 is in the subtree rooted at root
 * ret val = 2 means that nodes n2 is in the subrtree rooted at root
 * ret val = 3 means that both n1 and n2 are in the subtree rooted at root
 */
int  nearest_common_ancestor(BSTreeNode * root, BSTreeNode * n1, BSTreeNode * n2, BSTreeNode *& result)
{
	if (root == NULL)
		return 0;
	int v1 = nearest_common_ancestor(root->left, n1, n2, result);
	if (v1 == 3) 
		return 3;
	
	int v2 = nearest_common_ancestor(root->right, n1, n2, result);
	if (v2 == 3) 
		return 3;
	
	if (v1 == 1 && v2 == 2 || v2 == 1 && v1 == 2) {
		result = root;
		return 3;
	}

	if ((v1 == 1 && v2 == 0 || v1 == 0 && v2 == 1) && root->value == n2->value) {
		result = root;
		return 3;
	}

	if (v1 == 1 && v2 == 0 || v1 == 0 && v2 == 1)
		return 1;
	
	if ((v1 == 0 && v2 == 2 || v1 == 2 && v2 == 0) && root->value == n1->value) {
		result = root;
		return 3;
	}
	
	if (v1 == 0 && v2 == 2 || v1 == 2 && v2 == 0) 
		return 2;
	
	if (v1 == 0 && v2 == 0 && root->value == n1->value) 
		return 1;
	
	if (v1 == 0 && v2 == 0 && root->value == n2->value) 
		return 2;

	if(v1 == 0 && v2 == 0)
		return 0;
}

int main()
{
	BSTreeNode * nodes = (BSTreeNode *)malloc(sizeof(BSTreeNode)*10);
	nodes[1].value = 10;
	nodes[2].value = 7;
	nodes[3].value = 13;
	nodes[4].value = 6;
	nodes[5].value = 8;
	nodes[6].value = 11;
	nodes[7].value = 5;
	nodes[8].value = 9;
	nodes[9].value = 12;

	nodes[1].left = &nodes[2];
	nodes[1].right = &nodes[3];
	nodes[2].left = &nodes[4];
	nodes[2].right = &nodes[5];
	nodes[3].left = &nodes[6];
	nodes[3].right = NULL;
	nodes[4].left = &nodes[7];
	nodes[4].right = NULL;
	nodes[5].left = NULL;
	nodes[5].right = &nodes[8];
	nodes[6].left = NULL;
	nodes[6].right = &nodes[9];
	nodes[7].left = nodes[7].right = NULL;
	nodes[8].left = nodes[8].right = NULL;
	nodes[9].left = nodes[9].right = NULL;
	
	BSTreeNode * nca = NULL;
	nearest_common_ancestor(&nodes[1], &nodes[8], &nodes[9], nca);
	printf("%d's and %d's nearest common ancestor is: %d\n", nodes[8].value, nodes[9].value, nca->value);
	return 0;
}
